home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / documents / RFC / rfc1029.txt < prev    next >
Text File  |  1994-08-01  |  43KB  |  956 lines

  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                           G. Parr
  8. Request For Comments: 1029                         University of Ulster
  9.                                                                May 1988
  10.  
  11.  
  12.         A MORE FAULT TOLERANT APPROACH TO ADDRESS RESOLUTION FOR
  13.                     A MULTI-LAN SYSTEM OF ETHERNETS
  14.  
  15. STATUS OF THIS MEMO
  16.  
  17.    This memo discusses an extension to a Bridge Protocol to detect and
  18.    disclose changes in neighbouring host address parameters in a Multi-
  19.    LAN system of Ethernets.  The problem is one which is appearing more
  20.    and more regularly as the interconnected systems grow larger on
  21.    Campuses and in Commercial Institutions.  This RFC suggests a
  22.    protocol enhancement for the Internet community, and requests
  23.    discussion and suggestions for improvements.  Distribution of this
  24.    memo is unlimited.
  25.  
  26. ABSTRACT
  27.  
  28.    Executing a protocol P, a sending host S decides, through P's routing
  29.    mechanism, that it wants to transmit to a target host T located
  30.    somewhere on a connected piece of 10Mbit Ethernet cable which
  31.    conforms to IEEE 802.3.  To actually transmit the Ethernet packet, a
  32.    48 bit Ethernet/hardware address must be generated.  The addresses
  33.    assigned to hosts within protocol P are not always compatible with
  34.    the corresponding Ethernet address (being different address space
  35.    byte orderings or values).  A protocol is presented which allows
  36.    dynamic distribution of the information required to build tables that
  37.    translate a host's address in protocol P's address space into a 48
  38.    bit Ethernet address.  An extension is incorporated to allow such a
  39.    protocol to be flexible enough to exist in a Transparent Bridge, or
  40.    generic Host.  The capability of the Bridge to detect host reboot
  41.    conditions in a multi-LAN environment is also discussed, emphasising
  42.    particularly the effect on channel bandwidth.  To illustrate the
  43.    operation of the protocol mechanisms, the Internet Protocol (IP) is
  44.    used as a benchmark [6], [8].  Part 1 presents an introduction to
  45.    Address Resolution, whilst Part 2 discusses a reboot detection
  46.    process.
  47.  
  48. DEFINITIONS:
  49.  
  50.       CATENET: a group of IP networks linked together
  51.       IP     : Internet Protocol
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Parr                                                            [Page 1]
  59.  
  60. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  61.  
  62.  
  63.                                  PART 1
  64.  
  65. INTRODUCTION
  66.  
  67.    In the Ethernet, while all packets are broadcast, the hardware
  68.    interface selects only those with either the explicit hardware
  69.    broadcast address or the individual hardware address of this
  70.    interface.  Packets which do not have one of these two addresses are
  71.    rejected by the interface and do not get passed to the host software.
  72.    This saves a great deal of otherwise wasted effort by the host
  73.    software having to examine packets and reject them.  If the interface
  74.    hardware selected packets to pass to the host software by means of
  75.    the protocol address, there would be no need for any translation from
  76.    protocol to Ethernet address.  Although it is very important to
  77.    minimize the number of packets which each host must examine, so
  78.    reducing especially needless inspections, use of the hardware
  79.    broadcast address should be confined to those situations where it is
  80.    uniquely beneficial.  Perhaps if one were designing a new local
  81.    network one could eliminate the need for an address translation, but
  82.    in the real world of existing networks it fills a very important
  83.    purpose.  A rare use of the broadcast hardware address, which avoids
  84.    putting any processing load on the other hosts of the Ethernet, is
  85.    where hosts obtain the information they need to use the specific and
  86.    individual hardware addresses to exchange most of their packets.
  87.  
  88. REASONING BEHIND ADDRESS RESOLUTION
  89.  
  90.    The process of converting from the logical host address to the
  91.    physical Ethernet address has been termed ADDRESS RESOLUTION, and has
  92.    prompted research into a method which can be easily interfaced,
  93.    whilst at the same time remaining portable.
  94.  
  95.    The Ethernet requires 48 bit addresses on the physical cable [11] due
  96.    to the fact that the manufacturers of the LAN interface controllers
  97.    assign a unique 48 bit address during production.  Of course, Network
  98.    Managers do not want to be bothered using this address to identify
  99.    the destination at the higher-level.  Rather, they would prefer to
  100.    assign their logical names to the hosts within their supervision, and
  101.    allow some lower level protocol to perform a resolving operation.
  102.    Most of these logical protocol addresses are not 48 bits long, nor do
  103.    they necessarily have any relationship to the 48 bit address space.
  104.  
  105.    For example, IP addresses have a 32 bit address space [6], thus
  106.    giving rise to the need to distribute dynamically the correspondences
  107.    between a <PROTOCOLTYPE,PROTOCOL-ADDRESS> pair, and a 48 bit Ethernet
  108.    address.
  109.  
  110.  
  111.  
  112.  
  113.  
  114. Parr                                                            [Page 2]
  115.  
  116. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  117.  
  118.  
  119. EXAMPLE ARP OPERATION
  120.  
  121.    Here is a review of the operation of ARP as defined in RFC-826 [5].
  122.    Let hosts X and Y exist on the same Ethernet cable.  They have
  123.    physical Ethernet addresses EA(X), and EA(Y), and DoD Internet
  124.    addresses IPA(X), and IPA(Y).  Let the Ethernet type of Internet be
  125.    ET(IP).  Host X begins an application, and sooner or later wishes to
  126.    communicate an Internet packet to host Y.  Host X has knowledge of
  127.    the Internet address of Y, i.e., (IPA(Y)), and informs the lower
  128.    level that it wishes to talk to IPA(Y).  The lower-level subsequently
  129.    consults the ARP Module (ARM) to convert <ET(IP),IPA(Y)> into a 48
  130.    bit Ethernet address but because X has not talked to Y previously, it
  131.    does not have this information in its Translation Cache (TC).  It
  132.    discards (or queues) the Internet packet, and creates a new Address
  133.    Resolution packet with:
  134.  
  135.        PACKET FIELD             VALUE ASSIGNED
  136.  
  137.         HRDTYP                   ETHERNET
  138.  
  139.         PROTYP                   ET(IP)
  140.  
  141.         HRDLEN                   length (EA(X))
  142.  
  143.         PROTLEN                  length (IPA(X))
  144.  
  145.         ARPOPC                   REQUEST
  146.  
  147.         SOURCE HWR               EA(X)
  148.  
  149.         SOURCE PROT              IPA(X)
  150.  
  151.         TARGET HWR               don't know
  152.  
  153.         TARGET PROT              IPA(Y)
  154.  
  155.    It then broadcasts this packet to all hosts on the connecting cable.
  156.    Host Y picks up this packet and determines that it understands the
  157.    hardware type (Ethernet), that it speaks the indicated protocol
  158.    (Internet), and that the packet is for it, that is, TARGET PROTOCOL
  159.    ADDRESS = IPA(Y).  Replacing any previous entry, it enters the
  160.    information that <ET(IP),IPA(X) translates to EA(X).  It then learns
  161.    that this is an ARREQ packet, so it swaps fields, placing EA(Y) in
  162.    the new sender Ethernet address field SOURCE HARDWARE ADDRESS, EA(X)
  163.    as TARGET HARDWARE ADDRESS, IPA(X) as TARGET PROTOCOL ADDRESS, IPA(Y)
  164.    as SOURCE PROTOCOL ADDRESS, and sets the opcode to REPLY.  The packet
  165.    is then sent with direct routing address information to EA(X).  Thus,
  166.    Y now knows how to send to X, but X still doesn't know EA(Y).
  167.  
  168.  
  169.  
  170. Parr                                                            [Page 3]
  171.  
  172. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  173.  
  174.  
  175.    When X receives the ARREP packet from Y, it gets the address
  176.    information into its translation cache ET(IP),IPA(Y)>-->EA(Y),
  177.    notices that it is a REPLY, and discards the packet (i.e., disposes
  178.    of the dynamic packet buffer).  However, if the original Internet
  179.    Module packet had been queued, it could have been accessed and given
  180.    the full addressing information from the translation cache.
  181.    Alternatively, had it been discarded, the higher level would have
  182.    succeeded on a subsequent attempt, and the Internet packet would be
  183.    transmitted immediately.
  184.  
  185. OBTAINING GREATER NETWORKING RANGE
  186.  
  187.    There are many benefits to be gained in dividing a large multiuser
  188.    network into smaller, more manageable networks.  These include : Data
  189.    Security; Overall Network Reliability; Performance Enhancement; not
  190.    to mention the most obvious: Greater Networking Range.  In some
  191.    network technologies, cable length may be stipulated not to exceed a
  192.    certain range due to electrical limitations.  By installing a Bridge,
  193.    this restriction is effectively eliminated.  An important
  194.    consideration is the effect the induced Bridge delays will have on
  195.    the protocol timeouts in operation on each LAN/Subnet.  Careful
  196.    analysis of upper bounds on timeouts would have to be made in order
  197.    to gain full benefit from the increased range.  In the case of
  198.    Ethernet the following system parameters exist [11], [12]:
  199.  
  200.         - the bus bandwidth is 10Mbit/s
  201.  
  202.         - the maximum node-to-node cable length is 1500 m
  203.  
  204.         - the maximum point-to-point link cable length is 1000 m
  205.  
  206.         - the maximum number of repeaters between two nodes is two
  207.  
  208.         - the worst case end-to-end bus propagation delay is 22.5 us
  209.  
  210.         - the jam time after collision is 32bit
  211.  
  212.         - the minimum interframe time is 9.6 us
  213.  
  214.         - the slot size is 512 bit = 51.2 us
  215.  
  216.    Once a decision has being taken to subnet, the resulting subLANs may
  217.    be connected by including a Bridge to link them together and
  218.    providing a protocol which makes the collection of subnets appear as
  219.    a single network.  The basic idea of the Bridge providing 'repeater'
  220.    facilities would not suffice in this application.  Moreover, the
  221.    Bridge would have to have further 'intelligence' to enable it to
  222.    select those packets which are destined for remote networks based on
  223.  
  224.  
  225.  
  226. Parr                                                            [Page 4]
  227.  
  228. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  229.  
  230.  
  231.    the protocol address of the target host.  Thereby preventing it from
  232.    forwarding packets needlessly that will not be accepted.  If this
  233.    procedure was not adhered to, the channel bandwidth on the remote
  234.    networks would be inundated with packets, causing local valid traffic
  235.    to backoff and the efficiency of the respective networks to rapidly
  236.    decrease.
  237.  
  238.    One problem fundamental to the operation of the Bridge is how it
  239.    discovers on which LAN a particular host is interfaced.  If there are
  240.    only two LANs in the system, each will have a dedicated cache at the
  241.    Bridge, and when a packet is received at the particular interface,
  242.    the source host's address parameters are entered in the respective
  243.    LAN cache.  However, when we consider a Multi-LAN environment, the
  244.    procedure becomes more complicated.
  245.  
  246.    ___
  247.     |
  248.     |-----h3
  249.     |                                            E4
  250.     |-----hq                            |-----------------------|
  251.     |                _                             |        |
  252.     |-----hx        | | B1                         |        |
  253.     |---------------| |                            |        |
  254.     |-----h1        |_|                            |        |
  255.     |                |     h19                     |        |      ______
  256.     |                |    |                       | |        -----|______|  B4
  257.     |                |    |                       | | B3              |
  258.     |-----he       |-------------------| E2       |_|                 |
  259.     |                    |                         |                  |
  260.     |-----h5             |                         |                  |
  261.     |                    |                         |                  |
  262.     |                   ---                ---     |                  |
  263.    ---                  | |                 |-------                  |
  264.    E1                   | | B2              |                         |
  265.                         | |-----------------|                         |
  266.                         ---                 |                         |
  267.                                             |          |---------------------
  268.                                            ---                              |
  269.                                             E3                              |
  270.                                                                             |
  271.                       FIGURE 1.  A MULTI-LAN TOPOLOGY
  272.  
  273.  
  274.    In the normal set-up, whenever B3 or B4 would receive a packet on E4,
  275.    they would both update the caches on their E4 interface.  In
  276.    addition, a method must be provided to permit B4 to distinguish
  277.    between packets arriving on E4 from E1, E2, E3, and those which
  278.    actually originated on E4.
  279.  
  280.  
  281.  
  282. Parr                                                            [Page 5]
  283.  
  284. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  285.  
  286.  
  287.    This is so that packets can be categorized as being of remote or
  288.    local source and processed accordingly.  The most obvious solution is
  289.    for each Bridge to act as an AGENT and plug in its address as the
  290.    source of any packets it cascades to a remote network, instead of the
  291.    packet being cascaded with its original source address.  At Bridge
  292.    boot, it may issue a broadcast request for all locally connected
  293.    hosts/devices to return their local network protocol addresses.  On
  294.    subsequent receipt of this information, the Bridge could then update
  295.    the cache for each of its interfaces so that it would now have a base
  296.    from which to perform future operations.
  297.  
  298.    The alternative to this automatic procedure is to permit manual
  299.    intervention in the Bridge software which could be activated by the
  300.    network manager in order to key in the addresses of the hosts
  301.    connected to each LAN interface.
  302.  
  303.    Thus, having provided a means for the Bridge to obtain the original
  304.    state of the LAN addresses when it boots, how then does the Bridge
  305.    distinguish the arrival of a new host on the locally connected system
  306.    from transmissions which were sent from a remote source and cascaded
  307.    by an adjacent Bridge?  Two approaches are currently under
  308.    consideration to solve this problem, namely Explicit Subnets, and
  309.    Transparent Subnets [4], [7], [9], [14].
  310.  
  311.    In the Explicit Subnet approach, the location of the host in the
  312.    system is important.  The address of the host in the protocol suite
  313.    will reflect which subnet the host is interfaced to.  Consequently
  314.    the protocol address space is divided into a three level hierarchy of
  315.    <network,subnet,host>.  Within the Internet there are five addressing
  316.    divisions in operation [10], classes A, B, C, D, and E.  Classes D
  317.    and E relate to an addressing technique that will be used for
  318.    management of multi-casting groups and will not be discussed here.
  319.    With such a structure, it is possible to provide an address mask at
  320.    each interface so that received packets may have their source address
  321.    fields examined and compared with the address mask of this LAN.  In
  322.    so doing, the component which is being verified is actually the
  323.    subnet address.  If the masking operation is successful the source
  324.    must exist on this LAN, otherwise it must be remote.
  325.  
  326.    With the Transparent scheme, the first time a newly booted host
  327.    'speaks' it will be looking for addressing information (probably
  328.    using BOOTSTRAP [1], RARP [2] or ARP [5]).  Accordingly, the Bridge
  329.    will detect these respective requests and be in a position to perform
  330.    operations on the address parameters.  The current approach in
  331.    Transparent Subnetting is that before any such requests can be
  332.    cascaded by the Bridge to an adjacent LAN, that Bridge will place its
  333.    interface address parameters into the source address fields, thus
  334.    acting as the AGENT.  Therefore, this Bridge will 'see' either
  335.  
  336.  
  337.  
  338. Parr                                                            [Page 6]
  339.  
  340. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  341.  
  342.  
  343.    packets arriving from the remote Bridge address, or local packets.
  344.    By virtue of the RARP/ARP operation, which hosts perform when they
  345.    first come up, any hi-level packets received on to the network not
  346.    having the bridge address, and not having a mapping in the cache for
  347.    that LAN, can be considered as being remote.
  348.  
  349.    Currently, there is a move toward the Transparent subnet proposal
  350.    originally described by Postel [7].  This has been due mainly to
  351.    practical problems of incompatible implementations from different
  352.    vendors, and the restrictions that the Explicit address space place
  353.    on the adaptability of the system to change (class C addresses are
  354.    not flexible enough for the Explicit scheme).  It is also the opinion
  355.    of the Author of this paper that the Agent technique adopted by the
  356.    Bridges could have shortcomings in a dynamic environment which would
  357.    be detrimental to its operation; for example, where the bridges
  358.    themselves relocate or crash, or in the management of the "Agent For
  359.    Who" cache at the bridge.  Insofar as Loop Resolution and
  360.    SelfStabilization after failure are Bridge problems that need to be
  361.    addressed, it is strongly felt their satisfactory solution will be
  362.    supported by elimination of the Agent technique [13].
  363.  
  364. BRIDGE OPERATIONS
  365.  
  366.    Referring to figure 1, assume that at some stage during its
  367.    processing [E1H3] wishes to communicate with [E2H19].  [E1H3] obtains
  368.    knowledge of the Internet address of [E2H19] from its translation
  369.    cache, but will not require the knowledge that [E2H19] exists on a
  370.    completely different subnet.  [E1H3] calls its Internet Module to
  371.    transmit the packet.  As detailed, the usual procedure of passing
  372.    control to its ARM is performed in an attempt to obtain a
  373.    translation.  If we assume that [E1H3], and [E2H19] have not talked
  374.    before, the ARM in [E1H3] will not be able to resolve the addresses
  375.    on the first attempt.
  376.  
  377.    In such a case, an ARREQ packet is assembled and broadcast to all
  378.    hosts on the network [E1].  The packet traverses the cable and is
  379.    eventually picked up by the (B1) Bridge Address Resolution Module
  380.    (BARM), whereupon it determines whether or not it should intervene in
  381.    the request.  If the target is determined as remote (i.e., having no
  382.    match in the local cache), the BARM examines its Global Translation
  383.    Cache (GTC) to determine if it has an entry for <protocol,[E2H19]>.
  384.    Should a mapping be obtained at the Bridge, there is no need for the
  385.    broadcast REQUEST packet to be cascaded on to the remote network
  386.    [E2].  It is therefore assumed that the entries in the GTC reflect
  387.    the most current addressing information.  A match thus obtained, the
  388.    original ARREQ packet buffer is adapted as required and returned
  389.    directly to [E1H3] via the Bridges hardware interface IFE1.
  390.  
  391.  
  392.  
  393.  
  394. Parr                                                            [Page 7]
  395.  
  396. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  397.  
  398.  
  399.    On the other hand, should the Bridges' GTC have no information on
  400.    [E2H19], the BARM would have to perform the following steps:
  401.  
  402.       1.  drop the current ARREQ from [E1H3],
  403.  
  404.       2.  create its own ARREQ using the Bridge source addresses
  405.           and copy the target_internet_addr from the original
  406.           [E1H3] ARREQ packet,
  407.  
  408.       3.  broadcast the ARREQ on network E2 via network interface
  409.           IFE2, and go into a timeout awaiting a REPLY.
  410.  
  411.    Should this timeout period expire, a number of retries will be
  412.    permitted under control of the BARM.  Alternatively, if a REPLY is
  413.    received within the timeout interval, then the BARM will update its
  414.    GTC.  The ARM of [E1H3] next will attempt to transmit another ARREQ,
  415.    but this time a mapping will be obtained at the BARM'S GTC, and the
  416.    appropriate REPLY will be returned.
  417.  
  418.    Part 1 has described the state of the art of the behaviour of Address
  419.    Resolution.  Part 2 now extends the study to the more serious problem
  420.    of rebooting hosts in a multi-LAN system of Ethernets, and the
  421.    effects such changes have on the integrity of state information held
  422.    in ARP caches and routing tables.
  423.  
  424.                                  PART 2
  425.  
  426. THE CAPTURE OF REBOOTS
  427.  
  428.    Because Address Resolution packets are broadcast, all hosts on the
  429.    connecting cable including the Transparent Bridge will pick them up
  430.    and determine what they are.  Referring to figure 1, it may well be
  431.    the case that a host on E1 wishes to communicate with a fellow host
  432.    on the same physical ether.  Hence, if Hx wishes to talk to Hw on the
  433.    same ether, but has not done so previously, it will broadcast an
  434.    Address Resolution packet in the normal fashion.  The Bridge will
  435.    also 'see' the packet as it passes by, and will act as described
  436.    above, unless that is, there is some method of preventing it doing
  437.    so; there is no point in the Bridge invoking its ARM, and wasting
  438.    processing time if the problem is going to be resolved locally.
  439.  
  440.    It may occur however, that H1 wants to communicate with H5.  If
  441.    however, H5 has not talked with anyone before (i.e., it has been
  442.    "dormant"), H1 will issue an ARREQ.  The Bridge will not know that H5
  443.    is local because it won't have been entered in the local address
  444.    cache from previous conversations.  To avoid broadcasting an ARREQ to
  445.    all networks/subnets, one way around this problem is to set up the
  446.    contents of the local cache at Bridge startup time.  Therefore, the
  447.  
  448.  
  449.  
  450. Parr                                                            [Page 8]
  451.  
  452. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  453.  
  454.  
  455.    Bridge will already know not to intervene.  Thus, if the Bridge (with
  456.    2 nets) finds that a particular IP destination address is not in the
  457.    local cache of interface 1, it would have to examine its GTC and scan
  458.    it for a mapping.  Should no mapping be obtained at interface 2, one
  459.    of two possibilities exist:
  460.  
  461.         1. the target host doesn't exist locally
  462.  
  463.         2. the caches are corrupt (the eventuality of this should
  464.            be negligible!)
  465.  
  466.    If it is assumed that each of the translation caches contains have
  467.    the most recent addressing information regarding its own domain of
  468.    the network then, in this example, if the Bridge does not get a
  469.    mapping at the GTC it would appear that the host must exist remotely
  470.    from E1, and E2.
  471.  
  472.    Such a conclusion would ignore cases in which a host unplugs from a
  473.    particular hardware interface and plugs into another hardware
  474.    interface, or where logical names are reassigned to different
  475.    interfaces due to host user change.  Either of these events could
  476.    happen had the host being accessed on E2, which would mean that a
  477.    REBOOT has taken place.
  478.  
  479.    Anticipating these possiblities local caches are essential.  In
  480.    normal operation, the Bridge will process and forward IP packets
  481.    received from one network, and destined for another.  If the Bridge
  482.    picks up an ARREQ, it will first look for a mapping in its GTC before
  483.    discarding the original ARREQ, and transmitting its own to the remote
  484.    network.  In any case, the Bridge will always examine the local cache
  485.    entries at the receiving interface, so that it may determine if the
  486.    target address is local or remote.  When the Bridge first scans the
  487.    local cache, it does so with the source IP address as the key.  If no
  488.    mapping is retrieved, it then scans the GTC with the same key.
  489.    Should a mapping now be obtained, it remains for the Bridge to insert
  490.    the source IP into the local cache, where it has either been
  491.    previously deleted or corrupted.
  492.  
  493.    However, if the source IP exists in the respective local cache, the
  494.    validity of the source Ethernet address should also be verified by
  495.    examining the respective entry in the GTC.  A scan of the GTC is then
  496.    performed with <protocol,source_prot_addr> as the key.  If a mapping
  497.    is retrieved, the respective <et_addr> should be checked against the
  498.    source Ethernet address in the packet header.  If the addresses do
  499.    not match, then we have uncovered a Hardware Reboot condition (i.e.,
  500.    a change in Ethernet ID).  On the other hand, should the scan of the
  501.    GTC with <protocol,source_prot_addr> fail to obtain a mapping, then
  502.    the Bridge would scan the GTC with the current Ethernet address in
  503.  
  504.  
  505.  
  506. Parr                                                            [Page 9]
  507.  
  508. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  509.  
  510.  
  511.    the packet header.  If this obtains a mapping, then a Protocol Reboot
  512.    condition (i.e., change in logical ID) has been detected.
  513.  
  514.    In the next section, the implications of these forms of 'Reboot' are
  515.    discussed.
  516.  
  517. REBOOT SCENARIO
  518.  
  519.    In normal operation, packets will uneventfully traverse each subnet
  520.    either as complete Internet packets, broadcast ARREQ's, or direct
  521.    ARREP's.  The Bridge attached to each subnet will 'hear', and 'see'
  522.    all packets as they travel past its connected interfaces.  Because of
  523.    the existence of the local caches at each interface, the Bridge can
  524.    decide whether or not to intervene.  In general circumstances, each
  525.    host on the Catenet will have a translation cache containing
  526.    <protocol,source_prot_addr,source_et_addr> entries for all packets it
  527.    has observed.  Most of these entries will have been due to processing
  528.    ARREQ packets, which were broadcast, and by receiving REPLY packets.
  529.    In accordance with the foregoing , the Bridge will have a cache
  530.    attached to each subnet interface containing entries for protocol
  531.    addresses.
  532.  
  533.    Within the Bridge's Global Translation Cache (GTC) will be entries of
  534.    all <protocol,source_prot_addr,source_hrd_addr> triplets relating to
  535.    valid hosts which have been recognised.  If we assume that we have
  536.    just connected up a Catenet such as that illustrated in figure 1,
  537.    then at power-up no stations will have knowledge about their
  538.    neighbours.  If the Bridges are to remain transparent, the
  539.    translation caches at each host will be totally empty.  The only
  540.    addressing details that will be in existence will be the protocol
  541.    addresses stored in the local caches of the Bridges.
  542.  
  543.    The hosts subsequently begin to run applications and will want to
  544.    communicate with one another.  The first ARREQ is broadcast on the
  545.    respective subnet and all hosts, including the Bridge's interface to
  546.    the subnet, will pick it up and store the details.  If, for example,
  547.    Hx issues an ARREQ for Hq, the Bridge will not intervene since there
  548.    is no need (providing no reboot has occurred at Hq).  However, if Hx
  549.    wishes to talk with Hz, B1 will determine that the target IP in the
  550.    respective ARREQ does not exist in the local cache of IFE1, so it
  551.    will examine the GTC, with the <protocol,target_prot_addr> of Hw as
  552.    the key.
  553.  
  554.    It is assumed that there will be a timeout mechanism in operation at
  555.    the source of any packet.  In addition, the Bridge may also place the
  556.    target address in a 'search list' of currently sought hosts, so as to
  557.    prevent ARREQs from different sources being cascaded for the same
  558.    target.  Under these conditions, Hx may re-issue its original ARREQ,
  559.  
  560.  
  561.  
  562. Parr                                                           [Page 10]
  563.  
  564. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  565.  
  566.  
  567.    but will be ignored until the host Hw has replied to the ARREQ
  568.    transmitted by the Bridge.
  569.  
  570. NORMAL RUNNING STATE
  571.  
  572.    Assuming that a few ARP's have been issued, IP packets will start
  573.    traversing the Catenet with full addressing information.  Again, the
  574.    Bridges will 'see' all the packets.  If we extend the situation one
  575.    step further, and assume that several conversations have taken place
  576.    across the Catenet, there will be entries in the translation caches
  577.    of the hosts concerned, regarding the
  578.    <protocol,target_prot_addr,target_hrd_addr> triplets of those hosts
  579.    with which the conversations took place.  The Bridges also, will have
  580.    details in their GTC's for packets which they cascaded.
  581.  
  582.    If a host is relocated, any connections initiated by that host will
  583.    still work, provided that its own translation cache is cleared when
  584.    it does physically move.  However, any connections subsequently
  585.    initiated to it by other hosts on the Catenet will have no particular
  586.    reason to know to discard their old translation for that host.
  587.    Ideally, 48 bit Ethernet addresses will be unique and fixed for all
  588.    time.
  589.  
  590. RECOGNITION OF THESE REBOOT CONDITIONS
  591.  
  592.    With reference to figure 1, assume that for some reason a fault
  593.    occurs on the hardware interface of <E1He>.  The result of this is
  594.    that a new interface is installed with a newly acquired hardware
  595.    address.  When <E1He> is powered up, the previous contents of its
  596.    translation cache are cleared and it has no recollection of local, or
  597.    remote host addresses.  Accordingly, <E1He> begins to issue ARREQ's
  598.    to hosts it requires.  Whenever <E1He> transmits its first ARREQ, it
  599.    could be termed a 'HELLO PACKET', since everyone on the subnet can
  600.    pick up the packet, and store the relevant information in their
  601.    translation caches.  Within hosts, a mapping will be found on the old
  602.    <protocol,source_prot_addr> pair, and the current <et_addr> of the
  603.    packet header will replace whatever is entered in the translation
  604.    cache.
  605.  
  606.    At this point it would be easy for each host with an entry to
  607.    recognise the Hardware Reboot situation and inform the subnet with a
  608.    respective broadcast reboot packet.  But allowing such a procedure
  609.    would be extremly inefficient on the broadcast medium, and would
  610.    drastically outweigh any improvements in performance which might be
  611.    obtained in the long term.  In any case, given the fact that the
  612.    ARREQ is broadcast, all stations on the subnet will recognise the
  613.    reboot.  The important point to consider is the effect such a reboot
  614.    will have on subsequent conversations which are initiated remotely.
  615.  
  616.  
  617.  
  618. Parr                                                           [Page 11]
  619.  
  620. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  621.  
  622.  
  623.    Can redundant transmissions be thwarted before they tie up processing
  624.    time on hosts en-route to the rebooted target?  How these
  625.    difficulties are resolved is critical to the level of performance
  626.    obtained in a Catenet configuration.  Since it is not optimal for
  627.    hosts to inform the system of a reboot, it is left to the Bridge.
  628.    Whenever the Bridge receives a packet, be it IP, or ARP, it examines
  629.    the source address parameters in the packet header, in the hope of
  630.    detecting any incompatibilities between them and the entries in its
  631.    caches.  There are three distinct possibilities, namely, a difference
  632.    in the 48 bit hardware address only, a difference in the protocol
  633.    address, and two completely new addresses.  If an incompatibility is
  634.    discovered, a "REBOOT" packet is constructed and issued on all remote
  635.    interfaces containing the appropiate information, allowing Bridges to
  636.    update their GTC's and generic hosts their ARP caches.
  637.  
  638.    The structure of the Reboot packet is as depicted in figure 2.
  639.  
  640.     0                   1                   2                   3
  641.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  642.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  643.    | P A C K E T     O P C O D E   |REB OPC|      S O U R C E      |
  644.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  645.    |        H A R D W A R E            A D D R E S S               |
  646.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  647.    |       S O U R C E   P R O T O C O L     A D D R E S S         |
  648.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  649.    |     M U L T I C A S T   T A R G E T    H A R D W A R E        |
  650.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  651.    |    A D D R E S S      |   M U L T I C A S T     T A R G E T   |
  652.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  653.    |   P R O T O C O L     |
  654.    +-+-+-+-+-+-+-+-+-+-+-+-+
  655.  
  656.           ---------> NEXT FOLLOWS A VARIANT FIELD ON REBOOT  OPCODE
  657.  
  658.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  659.    |  O L D         S O U R C E        H A R D W A R E             |
  660.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  661.    |  A D D R E S S        |
  662.    +-+-+-+-+-+-+-+-+-+-+-+-+
  663.  
  664.     OR
  665.  
  666.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  667.    |  O L D     S O U R C E    P R O T O C O L      A D D R E S S  |
  668.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  669.  
  670.                           FIGURE 2. REBOOT PACKET
  671.  
  672.  
  673.  
  674. Parr                                                           [Page 12]
  675.  
  676. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  677.  
  678.  
  679.    The following definitions apply:
  680.  
  681.         PACKET FIELD              VALUE
  682.  
  683.         OPCODE                    REBOOT
  684.  
  685.         REBOOT OPCODE             HARDWARE
  686.  
  687.         REBOOT OPCODE             PROTOCOL
  688.  
  689.    The format is then as follows:
  690.  
  691.         48 bit broadcast Ethernet address for the destination,
  692.  
  693.         48 bit Ethernet address of source Bridge,
  694.  
  695.         16 bit Protocol type = PACKET OPCODE - REBOOT.
  696.  
  697.  
  698.    For completeness and error checking it may be an advantage to have a
  699.    field which specifies the length of addresses in the Ethernet and
  700.    protocol address spaces.  Thus, the Reboot packet structure contains
  701.    the following:
  702.  
  703.    FIELD          FIELD SIZE                    DESCRIPTION
  704.  
  705.    HRDLEN          4 bit             byte length of Ethernet address
  706.  
  707.    PROTLEN         4 bit             byte length of Protocol address
  708.  
  709.  
  710.    SOURCE
  711.    PROTOCOL
  712.    ADDRESS        32 bit            current protocol address of host
  713.  
  714.    TARGET
  715.    PROTOCOL
  716.    ADDRESS        32 bit           broadcast target protocol address
  717.  
  718.    REBOOT
  719.    OPCODE          4 bit            will be either PROTOCOL or HARDWARE
  720.  
  721.  
  722.    if   PROTOCOL       32 bit         old protocol address
  723.  
  724.    else HARDWARE       48 bit         old hardware  address
  725.  
  726.  
  727.  
  728.  
  729.  
  730. Parr                                                           [Page 13]
  731.  
  732. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  733.  
  734.  
  735.    As shown, depending on the REBOOT-OPCODE, the structure will continue
  736.    with either the 48 bit old hardware address or the 32 bit old
  737.    protocol address.  The choice of a variant packet structure is for
  738.    reasons of curtailing the size of the packet to the fields that are
  739.    truely necessary in each situation.  From this Reboot packet
  740.    structure, the process of generating such a packet can be considered.
  741.    When the Bridge algorithm detects a reboot, it should create a reboot
  742.    packet structure containing the relevant addressing information and
  743.    subsequently multicast it on the interface(s) which access(es) the
  744.    remote subnet(s).  The decision as to which interface(s) is/are
  745.    local, and which is/are remote, can be resolved automatically
  746.    whenever a packet is received.  With respect to this packet transfer
  747.    the receive interface at the Bridge becomes local, and all others are
  748.    tagged as remote.
  749.  
  750.    Thus, hosts on the subnet remote from the reboot are informed of the
  751.    situation immediately as it is detected by the Bridge.  In the
  752.    Catenet configuration illustrated in fig 1, this will have the effect
  753.    of updating the Translation Cache within each host, whenever it
  754.    receives the packet.  If for example, <E4Hw> reboots under hardware,
  755.    B3 will detect this occurance.  There is no reason for the subnets
  756.    E1, E2, E3 to be aware of this episode.  In normal operation, B3 will
  757.    recognise the reboot from the first ARREQ issued from <E4Hw>.  With
  758.    this reboot detection facility, B3 will be in a position to inform
  759.    the hosts on E1, E2, and E3.  B3 can then create and issue the Reboot
  760.    packet via its interface with E3.  When B3 picks it up, it will
  761.    update its own caches and subsequently cascade the packet onto E2,
  762.    where it will be passed on to E1 via B1.
  763.  
  764. ARGUMENTS FOR REBOOT PACKETS
  765.  
  766.    It is envisaged that introducing Reboot packets, will serve to
  767.    enhance the bandwidth achievable within a Catenet system.  Problems
  768.    of addressing 'dead' hosts will no longer exist in a correctly
  769.    functioning configuration.  Translation Caches will have on hand the
  770.    most recent addressing information available, which should also serve
  771.    to enhance the performance of the routing strategy in operation.
  772.    Multiple, redundant processing of packets destined for 'dead' hosts
  773.    will be avoided.  Weighing this against the processing involved with
  774.    a single multicast of Reboot packets, it is expected that the latter
  775.    will be is the most economically viable in relation to the long-term
  776.    traffic presented to the system.
  777.  
  778. CONCLUSION
  779.  
  780.    It appears that reboots are becoming increasingly common on internet
  781.    networks.  Many sites use Personal Computers (PC) as terminals and
  782.    the typical way to finish a session is to switch them off!  With the
  783.  
  784.  
  785.  
  786. Parr                                                           [Page 14]
  787.  
  788. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  789.  
  790.  
  791.    increasing popularity of multitasking Operating Systems on these
  792.    types of machines, problems are more likely to occur, particularly
  793.    when the PCs are diskless, or participating in a distributed file
  794.    system of some kind.  Given the importance of correct addressing in
  795.    communications networks running Ethernet, it is anticipated the
  796.    reboot mechanism described will serve to improve the correctness and
  797.    validity of the protocol/network address mappings which may be stored
  798.    in the translation caches.  To this degree, simulation is expected to
  799.    show that the volume of invalid traffic will decrease, to the benefit
  800.    of hosts, Bridges and servers alike.  Likewise, ratification of the
  801.    routing policy is anticipated and since redundant/obsolete packets
  802.    will be thwarted, the efficient utilization of available channel
  803.    bandwidth across the catenet is also expected to improve.  Thus,
  804.    effectively increasing Catenet throughput for 'valid' packets, and
  805.    therefore enhancing the level of service provided to the end users.
  806.  
  807.    It is obvious that the proposed scheme implies the alteration of the
  808.    packet processing code in Bridges/Gateways.  The point to remember is
  809.    the increased favour with which larger, more complex Multi-LAN
  810.    systems of Ethernets are being received.  The recent adaption of
  811.    extra telephone cables to serve as the transmission media for the
  812.    Ethernet can only result in installation costs being reduced, therein
  813.    making the Ethernet more attractive within large corporate buildings,
  814.    etc.  It is sensible to suggest that the probability of host address
  815.    re-assignment shall increase in proportion to the number of physical
  816.    systems attached, component failure rate (for whatever reason),
  817.    relocation of resources, and the size and turnover of the workforce
  818.    (i.e., people moving from one room to another).  Simulation
  819.    experiments are currently being developed to analyse the resultant
  820.    traffic patterns under this scheme, and it is hoped to highlight
  821.    thresholds where adoption of the scheme becomes a necessity.
  822.  
  823.    In addition, the Author is currently extending the boundaries of this
  824.    problem to encompass the reboot, or relocation of Bridges themselves.
  825.    Involved with this are the phenomena of loop resolution, load sharing
  826.    and duplicate packet suppression.  It is envisaged that a Self-
  827.    Stabilizationg Bridge Protocol will result that will be more "light-
  828.    weight" than those adhering to the Spanning Tree Algorithm.
  829.  
  830.    The Author would appreciate feedback/comments on this RFC.  My
  831.    network address is: CBAD13%UCVAX.ULSTER.AC.UK@CUNYVM.CUNY.EDU.
  832.  
  833. ACKNOWLEDGEMENTS
  834.  
  835.    The Author acknowledges with gratitute the help and comments
  836.    contributed by Mr. Piotr Bielkowitz (Supervisor) of the Computing
  837.    Science Department, and the time devoted my Mr. Raymond Robinson for
  838.    painstakingly preparing the first draft of this paper on 'Pagemaker'.
  839.  
  840.  
  841.  
  842. Parr                                                           [Page 15]
  843.  
  844. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  845.  
  846.  
  847.    Thanks are due also to Dr. M. W. A. Smith of Information Systems for
  848.    his assistance.  Finally, this work was supported under a grant from
  849.    the Department of Education for Northern Ireland of which the Author
  850.    is extremely grateful.
  851.  
  852. REFERENCES
  853.  
  854.    [1]  Croft, Bill, and John Gilmore, "Bootstrap Protocol", RFC-951,
  855.         Stanford University, September 1985.
  856.  
  857.    [2]  Finlayson, Mann, Mogul, and Theimer, "A Reverse Address
  858.         Resolution Protocol", RFC-903, Computer Science Dept, Stanford
  859.         University, June 1984.
  860.  
  861.    [3]  Lorimer, Alan, and Jim Reid, "ARP Information Communique",
  862.         Computer Science Dept, Strathclyde University, 1987.
  863.  
  864.    [4]  Mogul, Jeffrey, "Internet Subnets", RFC-917, Computer Science
  865.         Dept, Stanford University, October 1984.
  866.  
  867.    [5]  Plummer, David, "An Ethernet Address Resolution Protocol", RFC-
  868.         826, MIT, November 1982.
  869.  
  870.    [6]  Postel, Jon, "DARPA Internet Program Protocol Specification",
  871.         RFC-791, USC/Information Sciences Institute, September 1981.
  872.  
  873.    [7]  Postel, Jon, "Multi-LAN Address Resolution", RFC-925,
  874.         USC/Information Sciences Institute, October 1984.
  875.  
  876.    [8]  Postel, Jon, Carl Sunshine, and Danny Cohen, "The ARPA Internet
  877.         Protocol", Computer Networks, no. 5, pp. 261-271, 1981.
  878.  
  879.    [9]  Postel, Jon, and Jeff Mogul, "Internet Standard Subnetting
  880.         Procedure", RFC-950, USC/Information Sciences Institute and
  881.         Stanford University, August 1985.
  882.  
  883.    [10] Reynolds, Joyce, and Jon Postel, "Assigned Numbers", RFC-1010,
  884.         USC/Information Sciences Institute, May 1987.
  885.  
  886.    [11] "The Ethernet: a local area network, data link layer and
  887.         physical layer specification", Version 1.0 DEC, Intel and Xerox
  888.         Corporations, USA 30 September 1980).
  889.  
  890.    [12] Hughes, H.D., and L. Li, "Simulation model of an Ethernet",
  891.         Computer Performance, Vol 3, no. 4, December 1982.
  892.  
  893.    [13] Parr, Gerald P., "Address Resolution For An Intelligent
  894.         Filtering Bridge Running On A Subnetted Ethernet System", ACM
  895.  
  896.  
  897.  
  898. Parr                                                           [Page 16]
  899.  
  900. RFC 1029           Fault Tolerant ARP for Multi-LANs            May 1988
  901.  
  902.  
  903.         SIGCOMM Computer Communication Review, (July/August 1987), vol.
  904.         17, no. 3.
  905.  
  906.    [14] Smoot, Carl-Mitchell, and John S. Quarterman, "Using ARP to
  907.         Implement Transparent Subnet Gateways", RFC-1027, Texas Internet
  908.         Consulting, October 1987.
  909.  
  910.  
  911.  
  912.  
  913.  
  914.  
  915.  
  916.  
  917.  
  918.  
  919.  
  920.  
  921.  
  922.  
  923.  
  924.  
  925.  
  926.  
  927.  
  928.  
  929.  
  930.  
  931.  
  932.  
  933.  
  934.  
  935.  
  936.  
  937.  
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954. Parr                                                           [Page 17]
  955.  
  956.